package 剑指Offer._5160;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/16 14:30
 * 二叉搜索树的第k大节点
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 * 算法：二叉树
 * 由于是二叉搜索树，左子树的值 < 根值 < 右子树的值
 * 所以中序遍历二叉搜索树，会得到从小到大排序的数组
 * 因为要求第 k 大，所以从右子树开始遍历
 */
public class _54 {

    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.right;
            }
            if (stack.isEmpty()) break;
            root = stack.pop();
            --k;
            if (k == 0) return root.val;
            root = root.left;
        }
        return -1;
    }


}
